package hot100;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/22 14:47
 */

import java.util.*;

public class Test {

    String map [] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> solve(String s) {
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        recursion(0,s,map,list,sb);
        return list;
    }

    public void recursion(int index,String s,String map[],List<String> list , StringBuilder path){
        if(index == s.length()){
            list.add(path.toString());
            return ;
        }
        int i = s.charAt(index) - '2';
        for (char ch : map[i].toCharArray()){
            path.append(ch);
            recursion(index + 1,s,map,list,path);
            path.deleteCharAt(path.length() - 1);
        }
    }




    public int[] solve2(int nums[],int target){
        int l = binaryLeft(nums,target), r = binaryRight(nums,target);
        r = nums[r] == target ? r : - 1;
        l = nums[l] == target ? r : -1;
        return new int[]{l,r};
    }


    // <= x 的 右边界
    public int binaryRight(int nums[],int target){
        int l = 0,r = nums.length - 1;
        while(l < r){
            int mid =l + r  + 1>> 1;
            if(nums[mid] >target){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return l;
    }
    public int binaryLeft(int nums[],int target){
        int l = 0,r = nums.length - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }


}
